package xhhx.test;

public class MiniSpanTree {
    public static void Test() {
//        int[] v = {1, 2, 3, 4, 5, 6};
//        Prim prim = new Prim(v);
//        prim.InsertArc(1, 2, 6);
//        prim.InsertArc(1, 4, 5);
//        prim.InsertArc(1, 3, 1);
//
//        prim.InsertArc(2, 3, 5);
//        prim.InsertArc(3, 4, 5);
//
//        prim.InsertArc(2, 5, 3);
//        prim.InsertArc(3, 5, 6);
//        prim.InsertArc(5, 6, 6);
//        prim.InsertArc(3, 6, 4);
//        prim.InsertArc(4, 6, 2);
//
//        prim.Print();
//        prim.Gen(1);
        int[] v = {1, 2, 3, 4, 5, 6};
        Kruskal kruskal = new Kruskal(v, 10);
        kruskal.InsertArc(1, 2, 6);
        kruskal.InsertArc(1, 4, 5);
        kruskal.InsertArc(1, 3, 1);

        kruskal.InsertArc(2, 3, 5);
        kruskal.InsertArc(3, 4, 5);

        kruskal.InsertArc(2, 5, 3);
        kruskal.InsertArc(3, 5, 6);
        kruskal.InsertArc(5, 6, 6);
        kruskal.InsertArc(3, 6, 4);
        kruskal.InsertArc(4, 6, 2);

        kruskal.Gen();
    }

    public static class Prim {
        private int count;
        private int edgeCount;
        private int[] vertex;
        private int[][] matrix;
        public Prim(int[] vertex) {
            this.count = vertex.length;
            matrix = new int[count][count];
            this.vertex = vertex;
            for (int i = 0; i < count; i++) {
                for (int j = 0; j < count; j++) {
                    matrix[i][j] = 9;
                }
            }
        }

        public void Gen(int startV) {
            ClosedEdge[] closed = new ClosedEdge[count];
            int k = Locate(startV);
            for (int i = 0; i < count; i++) {
                if (i != k) {
                    closed[i] = new ClosedEdge();
                    closed[i].lowcast = matrix[i][k];
                    closed[i].v = startV;
                }
            }
            closed[k] = new ClosedEdge();
            closed[k].lowcast = 0;
            for (int i = 1; i < count; i++) {
                k = Min(closed);
                int u0 = closed[k].v;
                int v0 = vertex[k];
                System.out.println(u0 + "-" + v0);

                closed[k].lowcast = 0;
                for (int j = 0; j < count; j++) {
                    if (matrix[k][j] < closed[j].lowcast) {
                        closed[j].v = v0;
                        closed[j].lowcast = matrix[k][j];
                    }
                }
            }
        }

        private int Min(ClosedEdge[] closed) {
            ClosedEdge min = new ClosedEdge();
            min.lowcast = 9;
            int m = 0;
            for (int i = 0; i < closed.length; i++) {
                if (closed[i].lowcast == 0) {
                    continue;
                }
                if (closed[i].lowcast < min.lowcast) {
                    min = closed[i];
                    m = i;
                }
            }

            return m;
        }

        public int Locate(int v) {
            for (int i = 0; i < vertex.length; i++) {
                if (vertex[i] == v) {
                    return i;
                }
            }
            System.out.println("v:" + v + "not find");
            return -1;
        }

        public void InsertArc(int v, int w, int weight) {
            int i = Locate(v);
            int j = Locate(w);
            matrix[i][j] = weight;
            matrix[j][i] = weight;
            edgeCount++;
        }

        public void Print() {
            System.out.println("v:" + count + " edge:" + edgeCount);
            for (int i = 0; i < count; i++) {
                for (int j = 0; j < count; j++) {
                    int num = matrix[i][j] == 9 ? 0 : matrix[i][j];
                    System.out.print(num + "\t");
                }
                System.out.print("\n");
            }
        }

        public static class ClosedEdge {
            int v;
            int lowcast;
        }
    }

    public static class Kruskal{
        static class Edge{
            int head;
            int tail;
            int weight;
        }

        public int count;
        Edge[] edges;
        int[] vertex;
        int[] vertexBelong;

        public Kruskal(int[] vertex, int edgeCount){
            this.vertex = vertex;
            vertexBelong = new int[vertex.length];
            edges = new Edge[edgeCount];
        }

        public void Sort(){
            for (int i = 0; i < edges.length; i++){
                for (int j = 1; j < edges.length -i;j++){
                    if (edges[j-1].weight > edges[j].weight){
                        Edge temp = edges[j-1];
                        edges[j-1] = edges[j];
                        edges[j] = temp;
                    }
                }
            }
        }

        public void Gen(){
            Sort();
            for (int i = 0; i < vertexBelong.length; i ++){
                vertexBelong[i] = i;
            }
             for (int i = 0; i < edges.length; i++){
                int m = Locate(edges[i].tail);
                int n = Locate(edges[i].head);

                int vs1= vertexBelong[m];
                int vs2 = vertexBelong[n];
                if (vertexBelong[m] != vertexBelong[n]){
                    System.out.println(vertex[m] + "-" + vertex[n]);
                    for (int j = 0; j < vertexBelong.length;j++){
                        if (vertexBelong[j] == vs1){
                            vertexBelong[j] = vs2;
                        }
                    }
                }
            }
        }

        public int Locate(int v) {
            for (int i = 0; i < vertex.length; i++) {
                if (vertex[i] == v) {
                    return i;
                }
            }
            System.out.println("v:" + v + "not find");
            return -1;
        }

        public void InsertArc(int tail, int head, int weight){
            edges[count] = new Edge();
            edges[count].tail = tail;
            edges[count].head = head;
            edges[count].weight = weight;
            count++;
        }
    }
}



